//package leetcode;
//
//class Solution {
//    public int fib(int n) {
//        if (n == 0) {
//            return 0;
//        }
//        if (n == 1) {
//            return 1;
//        }
//        return fib(n - 1) + fib(n - 2);
//    }
//
//
////   public final int MOD = 1000000007;
////    public int fib(int n) {
////        int[] arr = new int[n+1];
////        if(n < 2){
////            arr[n] = n;
////        }else {
////            arr[0] = 0;
////            arr[1] = 1;
////        }
////        for(int i=2;i<=n;i++){
////            arr[i] = (arr[i - 1] + arr[i - 2]) % MOD;
////        }
////        return arr[n];
////    }
//
////    public int fib(int n) {
////        if(n < 2){
////            return n;
////        }
////        int f = 0;
////        int f1 = 0;
////        int f2 = 1;
////        for(int i=2;i<=n;i++){
////            f = (f1 + f2) % MOD;
////            f1 = f2;
////            f2 = f;
////        }
////        return f;
////    }
//
//}
//
//public class Test1 {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        int ret = solution.fib(3);
//        System.out.println(ret);
//    }
//}
